package com.honeywen.mymvc.leetcode;

import com.google.common.collect.Lists;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 746. 使用最小花费爬楼梯
 * https://leetcode-cn.com/problems/min-cost-climbing-stairs/description/
 *
 * @author wangwei
 * @date 2018/11/4 下午9:18
 */
public class ClimbStairTest {

    public static void main(String[] args) {
        int[] cost1 = {10, 15, 20}; // 15
        int[] cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}; //6
        int[] cost3 = {0, 1, 2, 2}; // 2
        int[] cost4 = {0, 2, 3, 2}; // 3
        System.out.println(minCostClimbingStairs(cost1));
        System.out.println(minCostClimbingStairs(cost2));
        System.out.println(minCostClimbingStairs(cost3));
        System.out.println(minCostClimbingStairs(cost4));
    }




    public static int minCostClimbingStairs3(int[] cost) {
        int n = cost.length;


        return 0;

    }
    public static int minCostClimbingStairs2(int[] cost) {

        int[] m = new int[cost.length + 1];
        return dp(cost, m, cost.length);

    }

    private static int dp(int[] cost, int[] m, int i) {
        if (i <= 1) {
            return 0;
        }

        if (m[i] > 0) {
            return m[i];
        }
        return m[i] = Math.min(dp(cost, m, i - 1) + cost[i - 1], dp(cost, m, i - 2) + cost[i - 2]);

    }


    public static int minCostClimbingStairs(int[] cost) {

        int len = cost.length;

        if (len == 2) {
            return cost[0] <= cost[1] ? cost[0] : cost[1];
        }

        int r1 = getResult1(cost);

        int r2 = getResult2(cost);

        return r1 <= r2 ? r1 : r2;

    }

        public static int getResult2(int[] cost) {
            int res = 0;
            int idx = cost.length;


            while (idx - 2 > -1) {
                int r1 = cost[idx - 1];
                int r2 = cost[idx - 2];
                if (r1 < r2) {
                    res += r1;
                    idx -= 1;
                } else {
                    res += r2;
                    idx -= 2;
                }

            }

            return res;

        }

        public static int getResult1(int[] cost) {
            int res = 0;
            int len = cost.length;
            int idx = -1;

            while (idx + 2 < len) {
                int r1 = cost[idx + 1];
                int r2 = cost[idx + 2];
                if (r1 < r2) {
                    res += r1;
                    idx += 1;
                } else {
                    res += r2;
                    idx += 2;
                }

            }

            return res;

        }


}
